В одном из
буддийских монастырей монахи уже тысячу лет занимаются перекладыванием дисков.
Они располагают тремя стержнями, на которых надеты диски разных размеров. В
начальном состоянии какое-то количество дисков было надето на первый стержень и
упорядочены по размеру – от меньших к большим сверху вниз. Монахи должны
переложить все диски с первого стержня на третий, выполняя единственное условие
– любой диск нельзя положить на диск меньшего размера. При перекладывании можно
использовать все три стержня. Монахи перекладывают один диск за одну секунду.
Как только они закончат свою работу, наступит конец света.
Ну разве это
по-монашески, приближать конец света? Неправильные какие-то монахи... :)
Поэтому нас не
будет интересовать ответ на вопрос, каким-то образом связанный с апокалипсисом,
а будет интересовать ответ на более привычный в обыденной нашей жизни вопрос: А
за какое наименьшее количество перекладываний монахи смогут завершить свою
работу, при условии, что перекладывают они диски оптимальным образом?
Вход. Количество дисков n (0 ≤
n ≤ 64), имеющихся
в распоряжении монахов. По странному стечению обстоятельств число дисков в этой
задаче не превышает количества клеток на обычной шахматной доске.
Выход. Наименьшее
количество перекладываний, за которое монахи смогут завершить свою работу.
|
Пример входа |
Пример выхода |
|
3 |
7 |
ханойские
башни
Для
перекладывания n дисков с первого на
третий стержень следует:
·
переложить n – 1 дисков с первого на второй стержень
·
переложить оставшийся один (наибольший)
диск с первого на третий стержень
·
переложить n – 1 дисков со второго на третий стержень
Пусть f(n) – искомое количество перекладываний.
Тогда получим рекуррентное соотношение:
f(n) = 2 * f(n – 1) + 1
Вычислим
несколько значений функции:
f(1) =
1,
f(2) = 2
* f(1) + 1 = 3,
f(3) = 2
* f(2) + 1 = 7,
f(4) = 2
* f(3) + 1 = 15
Методом
математической индукции докажем, что f(n)
= 2n – 1.
База
индукции. f(1) = 21 – 1 = 1.
Шаг
индукции. f(n + 1) = 2 *
f(n) + 1 = 2 * (2n – 1) + 1 = 2n+1
– 1.
Поскольку n ≤
64, то ответ на задачу 2n – 1 не помещается в 64-битовый знаковый тип.
Воспользуемся беззнаковым 64-битовым целым типом unsigned long long.
Читаем значение n.
scanf("%llu", &n);
Вычисляем res = 2n.
res = 1;
for (i = 0;
i < n; i++)
res = res * 2;
Выводим ответ res – 1 = 2n
– 1.
printf("%llu\n", res - 1);